package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿
 * 但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明
 * 请返回最后获胜者的分数。
 */
public class 纸牌问题动态规划 {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 4, 5, 1, 7, 4, 11, 13, 2, 4};

        int score = win(arr);

    }
    private static int win(int[] arr) {
        if (arr == null) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }

        int N = arr.length;
        int[][] fdp = new int[N][N];
        int[][] sdp = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sdp[i][j] = -1;
                fdp[i][j] = -1;
            }
        }

        int AScore = f(arr, 0, arr.length - 1, fdp, sdp);
        int BScore = s(arr, 0, arr.length - 1, fdp, sdp);
        return Math.max(AScore, BScore);//返回AB最大的那个分数
    }
    private static int s(int[] arr, int L, int R, int[][] fdp, int[][] sdp) {
        if (sdp[L][R] != -1) {
            return sdp[L][R];
        }
        //如果L==R,表示只剩一张牌了  但是当前是后手，，因此是拿不到的
        if (L == R) {
            return 0;
        }

        //第一种情况，对手拿最左边的牌 当前作为后手，那么在拿牌时在[L+1,R]范围上就是作为先手拿牌了
        int p1 = f(arr, L + 1, R, fdp, sdp);
        //第二种情况，对手拿最右边的, 当前作为后手，那么拿牌时在[L,R+1]范围上就是作为先手拿牌了
        int p2 = f(arr, L, R - 1, fdp, sdp);
        // 因为作为后手，肯定是后拿牌，拿到的肯定是较小的那个，两个人都绝顶聪明，肯定让对方拿到最小的牌
        sdp[L][R] = Math.min(p1, p2);
        return sdp[L][R];
    }

    /**
     * 该方法返回的是，作为先手，在arrayList.size()张牌中,能够获得的最大值
     *
     * @param arr
     * @param fdp
     * @param sdp
     * @return
     */
    private static int f(int[] arr, int L, int R, int[][] fdp, int[][] sdp) {
        if (fdp[L][R] != -1) {
            return fdp[L][R];
        }

        //如果L==R,表示只剩一张牌了  但是当前是先手，因此肯定是先手拿走
        if (L == R) {
            return arr[0];
        }
        //第一种情况，拿最左边的牌  当前作为先手，那么在下一次拿牌时在[L+1,R]范围上就是作为后手拿牌了
        int p1 = arr[L] + s(arr, L + 1, R, fdp, sdp);
        //第二种情况，拿最右边的。当前作为先手，那么在下一次拿牌时在[L,R+1]范围上就是作为后手拿牌了
        int p2 = arr[R - 1] + s(arr, L, R - 1, fdp, sdp);
        fdp[L][R] = Math.max(p1, p2);
        return fdp[L][R];
    }
}
